1842E - Tenzing and Triangle - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int long long
//typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
 
#define pb push_back
#define mp make_pair
//#define int long long
 
const ll MOD = 1e9 + 7;
 
const int MAXN = 6e5 + 5;


const int inf = 1e9;
struct Node {
	Node *l = 0, *r = 0;
	int lo, hi, mset = inf, madd = 0, val = -inf;
	Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of -inf
	Node(vi& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo)/2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = max(l->val, r->val);
		}
		else val = v[lo];
	}
	int query(int L, int R) {
		if (R <= lo || hi <= L) return -inf;
		if (L <= lo && hi <= R) return val;
		push();
		return max(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) mset = val = x, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = max(l->val, r->val);
		}
	}
	void add(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			if (mset != inf) mset += x;
			else madd += x;
			val += x;
		}
		else {
			push(), l->add(L, R, x), r->add(L, R, x);
			val = max(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo)/2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset != inf)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = inf;
		else if (madd)
			l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
	}
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


	int n, k, A; cin >> n >> k >> A;
	vector<vector<pii>> coords(MAXN);
	int sm = 0;
	rep(i, 0, n) {
		int x, y, c; cin >> x >> y >> c;
		coords[y].pb({x, c});
		sm += c;
	}

	vector<int> dp(k + 1, 0);
	vector<int> v(k + 1, 0);
	Node* g = new Node(v, 0, sz(v));

	int tot = 0;
	rep(i, 1, k + 1) {
		dp[i] = dp[i - 1];
		if (i > 1) g->add(0, i - 1, -A);
		for (auto [x, cost] : coords[k - i]) {
			if (x > 0) g->add(0, x, cost);
			tot += cost;
		}
		tot -= A;
		if (i > 1) dp[i] = max(dp[i], g->query(0, i - 1));
		dp[i] = max(dp[i], tot);
		g->add(i, i + 1, dp[i]);
	}

	cout << sm - dp[k] << endl;

    return 0;
}